1. Field of the Invention
This invention relates to a data protocol in a computer network, and in particular to a Quality of Service (QoS) metric for a data protocol for transmitting Internet Protocol (IP) data subject to QoS constraints in a wireless mobile ad-hoc network.
2. Description of the Related Art
A collection of wireless mobile xe2x80x9cnodesxe2x80x9d that form the network without any fixed infrastructure or centralized administration is typically referred to as a wireless mobile xe2x80x9cad hocxe2x80x9d network (MANET). Such networks are useful for when it is economically or physically impractical to provide a fixed infrastructure, or when urgency does not allow installation of a fixed infrastructure. For example, a class of students may need to interact with their computers during a lecture; business associates may wish to share files impromptu at an airport terminal; rescue workers may need emergency communications after an earthquake; or, soldiers may need mobile communications on a battle field. In these situations, the computer communications network cannot be xe2x80x9cterrestrial,xe2x80x9d i.e., it cannot have a fixed infrastructure or centralized administration; it must be a MANET.
Due to the limited range of the wireless transmission of each node in a MANET, a source node may need to enlist the aid of other intermediary transit nodes to forward data, usually grouped in xe2x80x9cpackets,xe2x80x9d to a destination node. A routing protocol finds a xe2x80x9cpath,xe2x80x9d xe2x80x9croute,xe2x80x9d or xe2x80x9cchannelxe2x80x9d for the data packets to travel from the source node to the destination node. FIG. 1 is a diagram of a conventional MANET. For example, a node C is not within a wireless transmission range 102 of a node A, and node A is not within a wireless transmission range 104 of node C. If node A and C want to exchange data packets, they may use node B as a transit node to forward data packets from node A to node C, and vice versa. It is practical to use transit node B because it is within both the wireless transmission ranges 102, 104 of node A and node C. Of course, the routing problem in a MANET may be more complicated than that in FIG. 1, due to mobile nodes and nonuniform propagation characteristics of wireless transmission.
Recently, MANETs have been supporting real-time Internet Protocol (IP) applications, such as telephony, and video streaming. Real-time IP applications (and any application that requires the transmission of time-sensitive data) need predictable network resources, to support predictable Quality of Service (QoS). QoS support entails providing an application with enough network resources so that it can function within acceptable performance limits. This support includes providing a minimum guaranteed bandwidth or special processing some packets. In IP telephony, for instance, the network must provide two xe2x80x9cflowsxe2x80x9d of dataxe2x80x94one flow in both directions between telephone users. The two flows must have a large enough bandwidth to carry digitized voice without introducing an annoying delay.
In both MANETs and terrestrial networks, however, data traffic congestion often frustrates providing sufficient network resources for QoS support for real-time applications. In a MANET, for instance, xe2x80x9cphysical layerxe2x80x9d impairments that are caused by noisy, poor-quality radio channels result in insufficient network resources. In addition to the Gaussian background noise of terrestrial networks, MANETs also have impulsive noise, multipathing, signal fading, unintentional interference from other users of the channel, and intentional enemy jamming. These all increase noise and reduce the quality of radio channels in MANETs.
Solutions to physical layer impairments include providing stronger data coding, finding an alternate route, or increasing the transmission power level. These solutions, however, usually increase congestion in the network. For example, stronger codes add resiliency to a channel, but effectively reduce available bandwidth. Further, when the bit error rate caused by channel impairments reaches a certain threshold, coding methods alone are insufficient to overcome the impairment and an alternate path is needed. For example, such a threshold may be a bit error rate (BER) of 10xe2x88x922 errors per second. Of course, finding an alternate route increases data congestion at other parts of the MANET. Lastly, increasing transmission power increases collisions and interference between nodes, which may reduce available bandwidth.
Another solution to the congestion problem is to over-engineer the network to provide more bandwidth. In a terrestrial network, over-engineering may include laying more coaxial or fiber optic cables. In a MANET, over-engineering may include increasing the frequency bands allocated to the MANET. It is expensive and inefficient to over-engineer a network, however, and this approach is not easily applied in MANETs.
Yet another solution to the congestion problem is to identify packets carrying real-time applications and provide them with special xe2x80x9cpriorityxe2x80x9d treatment. A widely known priority treatment is Differentiated Services (DS). Roughly speaking, DS marks special packets of data in a DS field in the packet. Nodes treat the specially marked packets according to an appropriate priority. DS does not identify individual flows, but provides a special treatment to an aggregate xe2x80x9cclassxe2x80x9d of flows, as specified in the Per Hop Behavior (PHB) that corresponds to a particular value in the DS field.
PHBs use well-known packet scheduling algorithms such as weighted fair queuing, or start time queuing. These algorithms ensure that a minimum bandwidth is allocated to a certain class of traffic. Because DS does not differentiate between individual flows, the guaranteed bandwidth is allocated to an aggregate of flows, differentiated from other aggregated flows by a different DS field value. In the DS approach, a class of traffic obtains a given portion of the network resources. In one extreme case, however, the portion allocated to a specific class is 100%, and effectively nothing is gained from the DS approach. Further, there may be too many data packets for the allocated bandwidth in a given class. In this case, packets from the class would be subject to congestion within its allocated resources, similar to a single class best-effort system.
Many other solutions to solve the congestion problem assume that a particular node in the MANET is likely to serve as a transit node to a very large number of flows, similar to a xe2x80x9cbackbonexe2x80x9d node in a high-speed terrestrial network. This assumption, however, is flawed because there usually is no identifiable backbone node in a MANET. MANET nodes, unlike terrestrial nodes, randomly assume transit responsibilities so that no one node is significantly more likely than another to serve as a transit node. Second, MANET nodes generally have a relatively low channel bit-rate that may saturate if acting as a backbone. Hence, no node in a MANET is likely to be a backbone node.
Most solutions to the congestion problem may also use xe2x80x9cmetricsxe2x80x9d to measure conditions of the network in order to manage congestion. There are several known QoS metrics that relate to the performance requirements of real-time applications, including delay, jitter, and throughput. Routing algorithms use QoS metrics to find a path that satisfies the QoS requirements. Calculating a metric to find a route that satisfies multiple constraints, however, is a computationally difficult problem.
Thus, there is a need to overcome congestion within a class, provide QoS service, allocate network resources for identified flows, without generating significant overhead data. More specifically, there is a need for improved routing of IP packets with QoS constraints over MANETs with an improved QoS metric.
This summary and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the detailed description, show several embodiments of the invention and, together with the description, explain the principles of the invention.
Methods and systems consistent with this invention manage data traffic in a network comprised of a plurality of nodes including a first node having at least one neighboring node. Such methods and systems determine a value indicative of a maximum unused bandwidth of the first node, receive from the at least one neighboring node data indicative of at least one maximum unused bandwidth of the at least one neighboring node, calculate a value indicative of a maximum available bandwidth of the first node from the value indicative of the maximum unused bandwidth of the first node and the received data indicative of the at least one maximum unused bandwidth, and allocate an air time for the first node to transmit data as a function of the maximum available bandwidth of the first node.
Such methods and systems use a decentralized algorithm that is run by the participating nodes in the MANET with a minimal amount of control packets contributing to network overhead.